1. Field of the Invention
The present invention relates to an arithmetic unit for performing a multidimensional discrete cosine transformation (DCT) or inverse discrete cosine transformation (inverse DCT). More particularly, the present invention relates to an arithmetic unit of a discrete cosine transformation (DCT)/inverse discrete cosine transformation (inverse DCT) included in an encoder and a decoder of image data.
2. Description of the Related Art
A discrete cosine transformation (DCT) is often used to compress image information since a method for processing the image information is simple in the discrete cosine transformation.
DCT and inverse DCT of an N-th order in M-dimensions are provided by the following formulas (1) and (2).
Namely, the DCT of the N-th order in M-dimensions is provided by the following formula (1). ##EQU1##
The inverse DCT of the N-th order in M-dimensions is provided by the following formula (2). ##EQU2##
In this case, C(u.sub.1), - - - , C(u.sub.M) are provided as follows. ##EQU3##
In the above formulas, f(i.sub.1, i.sub.2, - - - , i.sub.M) is set to an input of the DCT or an output of the inverse DCT. F(u.sub.1, u.sub.2, - - - , u.sub.M) is set to an output of the DCT or an input of the inverse DCT.
DCT and inverse DCT of an eighth order in two dimensions used for image compression are provided by the following formulas (3) and (4).
Namely, the DCT of the eighth order in two dimensions is provided by the following formula (3). ##EQU4##
The inverse DCT of the eighth order in two dimensions is provided by the following formula (4). ##EQU5##
In the case of image compression, f(i.sub.1, i.sub.2) corresponds to a pixel value of an original image or a restored image. F(u.sub.1, u.sub.2) corresponds to a pixel value of a compressed image.
In general, the DCT of the N-th order in M-dimensions can be realized by sequentially performing one-dimensional N-th order DCT M-times. For example, in the above two-dimensional eighth order DCT, one-dimensional eighth order DCT is first executed in a row or horizontal direction. Next, one-dimensional eighth order DCT is executed in a column or vertical direction with respect to DCT results in the row or horizontal direction. Thus, the above two-dimensional eighth order DCT can be realized. The two-dimensional eighth order DCT can be similarly realized even when the one-dimensional eighth order DCT is performed by inverting its arithmetic directional order.
Namely, the two-dimensional eighth order DCT in the above formula (3) can be decomposed into one-dimensional eighth order DCTs in row (horizontal) and column (vertical) directions as shown by the following formulas (5) and (6).
The one-dimensional eighth order DCT in the row or horizontal direction is provided by the following formula (5). ##EQU6##
The one-dimensional eighth order DCT in the column or vertical direction is provided by the following formula (6). ##EQU7##
In this case, F.sup.R (i.sub.1, u.sub.2) (i.sub.1, u.sub.2 =0, - - - , 7) shows an output value of a row transformation.
The above formulas (5) and (6) are also formed with respect to the inverse DCT.
For example, the following calculating methods are well known as an arithmetic method of the DCT and inverse DCT of the eighth order in one dimension.
(1) In a first arithmetic method, arithmetic or calculating formulas of the DCT and inverse DCT of the eighth order in one dimension are used as they are. In the following description, this first arithmetic method is called algorithm A.
(2) In a second arithmetic method, a high speed algorithm is used. This second arithmetic method is called algorithm B.
For example, the algorithm B uses a Lee system used for some of a DCT-dedicated LSI in development of other companies. As a reference literature, see Lee B. G, "A New Algorithm to Compute the Discrete Cosine Transform," IEEE Transactions on Acoustics, Speech, and Signal Processing, ASSP-32, no. 6, pp 1245-1245, December 1984.
In a general technique, the DCT and inverse DCT of the N-th order in M-dimensions are realized by repeatedly performing the DCT and inverse DCT of the N-th order in one dimension using the same arithmetic algorithm.
When an arithmetic unit of the DCT and inverse DCT of the N-th order in M-dimensions is realized by hardware, an error in arithmetic or calculated results is caused by truncation of intermediate results. This arithmetic error will next be described, particularly in the case of a two-dimensional eighth order inverse DCT used in an image compressing technique.
A mean square error is used as an evaluation value of an arithmetic accuracy when random numbers in a range from -258 to 255 are generated by 10,000 blocks in accordance with an evaluating method of an inverse DCT arithmetic accuracy prescribed in a coding system H.281 for a visual telephone and a television conference advised by Consultative Committee of International Telegraph Telephone (CCITT).
The mean square error in the entire blocks is provided as an average by the following formula (7). ##EQU8##
X.sub.b.sup.a =evaluation value, a: a pixel number from 1 to 84 within a block
X.sub.b.sup.a =reference value, b: a block number from 1 to 10000
The number of arithmetic or calculating operations is set to a number obtained by adding the number of multiplying operations and the number of adding operations to each other when the two-dimensional eighth order inverse DCT is calculated.
When the algorithm A is used in both the column and row directions, the number of arithmetic operations is equal to 128 (generally 2N.sup.2) and an arithmetic or calculating accuracy is equal to 0.005.
When the algorithm B is used in both the column and row directions, the number of arithmetic operations is equal to 41 (generally 2Nlog.sub.2 N-N+1) and the arithmetic accuracy is equal to 0.013.
In the inverse DCT calculation, a multiplier of 16 bits and an adder of 32 bits are used. Calculated results of the one-dimensional eighth order inverse DCT in the column direction are rounded to 16 bits. Calculated results (IDCT results) of the one-dimensional eighth order inverse DCT in the row direction are rounded to 9 bits. The above evaluation is performed with respect to these rounded results.
When the DCT and inverse DCT of the N-th order in multiple dimensions are performed by repeating the DCT and inverse DCT of the N-th order in one dimension using the same arithmetic algorithm as in the general technique, the arithmetic accuracy is high, but the number of arithmetic operations is large when the algorithm A is used in the DCT and inverse DCT of the N-th order in one dimension. Accordingly, an arithmetic operation speed is slow in this case. In contrast to this, when the algorithm B is used in the DCT and inverse DCT of the N-th order in one dimension, the number of arithmetic operations is small so that the arithmetic operation speed is fast, but the arithmetic accuracy is low.